The present invention relates to a method for determining elliptical curves, in particular elliptical curves which are suitable for cryptographic data processing. Further, a cryptographic method and a facility are based on the elliptical curves previously selected.
Cryptographic methods are used, among other purposes, for encrypting messages, signing documents and authenticating individuals or objects. Particularly suitable for this purpose are so-called asymmetric encryption methods, in which a participant is provided with both a private key, which is kept secret, and also a public key.
When encrypting a message, the sender makes use of the desired addressee's public key, and uses it to encrypt the message. Thereafter, only the addressee is in a position to decrypt the message again, using the private key known only to him.
When signing a document, the signatory uses his private key to calculate from the document an electronic signature. Other people can directly verify the signature, using the signatory's public key. However, only signatures which were produced using the associated private key can be verified using the public key. As a result of this unique assignment, and assuming that the private key is kept secret by the signatory, there is a unique assignment of the signature to the signatory and to the document.
In the case of authentication using a challenge-response protocol, a testing station communicates a request to a person asking them to calculate and send back a reply, using their private key. A positive authentication results if the testing station is able, using the public key of the individual to be checked, to verify the reply which is sent back.
As explained above, asymmetric cryptographic methods are based on a private and a public key. Here, the public key is generated from the private key by a predefined algorithm. What is important for cryptographic methods is that the reverse, that is the determination of the private key from the public key, should not be manageable within a finite time with the computing capacities which are available. This is the case if the key length of the private key is greater than a minimum length. This minimum length for the key depends on the algorithms used for the encryption and on the determination of the public key.
The operations using the public or private key call for a certain amount of computational effort. This depends on the algorithms used and also on the length of the keys used. In this situation it has proved advantageous to use encryption algorithms based on elliptical curves, because these provide high security with short key lengths. In the case of cryptographic methods based on elliptical curves there is, unlike other methods, as yet no known way of determining the private key from the public key for which the computational effort increases more slowly than exponentially as the key length increases. In other words, the security gain per additional bit of length for the key which is used is higher than for other methods. Hence significantly shorter key lengths can be used for practical applications.
An elliptical curve E is generally defined by a Weierstraβ equation, which is written as the following cubic equation:y2+a1xy+a3y=x3+a2x2+a4x+a5 
In this, a1 a2 a3 as as are constant chosen elements of a field K and the pairs (x, y) are points on the elliptical curve E and satisfy the Weierstraβ equation. For the cryptographic methods, a finite field K is selected. Accordingly, the number of points on the elliptical curve E is also finite, and is referred to below as the order ord(E) of the curve E. In addition, one formal point is introduced at infinity.
An abelian group structure G can be defined on the set of points on the elliptical curve. The operation of the abelian group structure is referred to below as addition, and is written additively. The addition of two arbitrary points on the elliptical curve gives a unique third point on this elliptical curve. Furthermore, it is possible in this way to define a scalar multiplication, which is defined as the multiple addition of a point to itself. Let P be a point on the elliptical curve E, s an integer and Q=sP the s-fold of the point P. Q is also a point on the elliptical curve. The determination of the scalar s for given points P and Q is referred to as the discrete logarithm problem for elliptical curves. For a suitable choice of the field K and the parameters of the elliptical curve E it is impossible to solve the discrete logarithm problem in a reasonable time with the computing facilities presently available. The security of cryptographic methods using elliptical curves rests on this difficulty.
The communication participant selects a scalar s as his private key, and keeps it secret. In addition, from a start point P he generates the public key Q as the scalar multiple of the start point. In respect of the start point P, there is agreement between the communication participants. Owing to the high computational cost of the discrete logarithm problem, it is not possible to determine the private key s from the public key Q, which is what gives cryptographic methods using elliptical curves their security. Another requirement to be met by the elliptical curves is that their order should be a large prime number or the product of a large prime number and a small number.
Cryptographic methods represent a compromise between an expected level of security and the computational cost for encrypting data. It is shown in DE 101 61 138 A1 that it is possible to determine the scalar multiple of a point solely by reference to the x-coordinates, without involving the y-coordinates. Appropriate computational rules are described for arbitrary fields in DE 101 61 138 A1. These permit significantly more efficient implementations of the point arithmetic to be achieved, e.g. a Montgomery ladder for the scalar multiplication, a smaller number of field multiplications per point addition and a smaller number of registers for the point representation and the intermediate results. However, with this method no check is made as to whether a point really is an element on the elliptical curve.
This produces the possibility of carrying out a side-channel attack. This involves communicating to an encryption facility an x-coordinate for a point which does not lie on the elliptical curve. In this connection, DE 10161138 A1 describes the fact that it is possible by this means to effect a partial reconstruction of the encryption facility's private key. To prevent such a side-channel attack, DE 10161138 A1 uses specially selected elliptical curves. In doing so, the twisted elliptical curves associated with the elliptical curves were used as the criterion. The associated twisted elliptical curve is defined as follows:y2+va1xy+a3y==x3+va2x2+v2a4xv3a5,where the parameters a1, a2, a3, a4, a6 are the parameters of the elliptical curves. The parameters v are all non-squares of the field K, if the characteristic of the field K is odd, or an element of the field K with trace 1. In accordance with DE 10161138 A1, all these twisted elliptical curves should also have an order which is a large prime number or the product of a large prime number with a small number.
In their article “The Static Diffie-Hellman Problem”, the authors Daniel R. L. Brown and Robert P. Gallant describe another possibility for a side-channel attack to spy out, completely or in part, a private key.
Against this background, one potential object is to provide a method which selects elliptical curves which, when subject to a side-channel attack, do not enable any conclusions to be drawn about the private key.
Accordingly, the following is provided:
A method for determining an elliptical curve which is suitable for cryptographic methods, with the following steps:
(a) provide an elliptical curve to be tested;
(b) determine the order of a twisted elliptical curve which is assigned to the elliptical curve to be tested;
(c) automatically check whether the order of the twisted elliptical curve is a strong prime number; and
(d) if the order of the twisted elliptical curve is a strong prime number, select the elliptical curve to be tested as an elliptical curve which is suitable for cryptographic method.
A method of processing data cryptographically with the following steps:
provide an elliptical curve, determined using the proposed method;
provide just one x-coordinate of a point;
provide a private key;
automatically apply a cryptographic encryption method to the x-coordinate, using the elliptical curve provided and the private key, to determine an encrypted x-coordinate; and
output a value based on the encrypted x-coordinate.
A facility for confirming the identify of a person or an object, having                a receiving device which is used for receiving a coordinate,        a storage device which keeps ready a private key for the person or the object,        a processing device which is used to process the coordinate which has been received, using the private key, where the processing is based on an elliptical curve which is selected in accordance with one of the methods 1 to 3, and        an output device which is set up to output the processed coordinate.        
The proposed method uses an elliptical curve for the cryptographic method only if the twisted elliptical curve for this elliptical curve has an order which is a strong prime number. A strong prime number P is defined by the following equation:P=1+r·q, where r is a small number, typically in the range up to 255, and q is a large prime number. Ideally, the strong prime number will be a so-called Sophie-Germain prime number, i.e. r is 2. The elliptical curves and the associated twisted elliptical curves conform to the definitions cited above. The proposed method prevents side-channel attacks which are based on x-coordinates which are communicated erroneously or on x-coordinates which are falsely communicated with malicious intent, where these x-coordinates do not correspond to any point on the selected elliptical curve. The proposed method is robust in the sense that even in the case of such x-coordinates it is not possible for an external device to spy out or partially determine the private key.
In accordance with one form of embodiment, the order of the twisted elliptical curve is determined by counting a number of points which lie on the twisted elliptical curve. Alternatively, the order of the twisted elliptical curve can also be determined on the basis of a determination of the order of the elliptical curve and the characteristic of the field. For this purpose, unique mathematical relationships between the different orders can be used. The counting of the points is effected using methods generally known to the specialist.
In one form of embodiment, an automatic check is made as to whether the order of the elliptical curve to be tested is a strong prime number, and the elliptical curve to be tested is then only selected for cryptographic methods if the order of the elliptical curve to be tested is a strong prime number.